class MyLinkedList{
  constructor(){
    this.head = null
    this.last = null
    this.size = 0
  }
  insert(index, data){
    if(index<0 || index>this.size) {
      throw new Error('超出链表节点范围')
    }
    let insertNode = new Node(data)
    if(this.size == 0) {
      this.head = insertNode
      this.last = insertNode
    } else if(index == 0) {
      insertNode.next = this.head
      this.head = insertNode
    } else if(this.size == index) {
      this.last.next = insertNode
      this.last = insertNode
    } else {
      let prevNode = this.get(index-1)
      insertNode.next = prevNode.next
      prevNode.next = insertNode
    }
    this.size++
  }
  remove(index){
    if(index<0 || index>=this.size) {
      throw new Error('超出链表节点范围')
    }
    let removeNode = null
    if(index == 0) {
      removeNode = this.head
      this.head = this.head.next
    } else if(index == this.size-1) {
      let prevNode = this.get(index-1)
      prevNode.next = null
      this.last = prevNode
    } else {
      let prevNode = this.get(index - 1)
      let nextNode = prevNode.next.next
      removeNode = prevNode.next
      prevNode.next = nextNode
    }
    this.size--
    return removeNode
  }

  get(index){
    if(index<0 || index>=this.size) {
      throw new Error('超出链表节点范围')
    }
    let temp = this.head
    for(let i = 0; i < index; i++){
      temp = temp.next
    }
    return temp
  }
  output() {
    let temp = this.head
    while(temp != null) {
      console.log(temp.element)
      temp = temp.next
    }
  }
}

class Node{
  constructor(data) {
    this.element = data
    this.next = null
  }
}

let myLinkedList = new MyLinkedList()
myLinkedList.insert(0,3)
myLinkedList.insert(0,4)
myLinkedList.insert(2,9)
myLinkedList.insert(3,5)
myLinkedList.insert(1,6)
myLinkedList.remove(0)
myLinkedList.output()